/// @file UnivHashFixedVector.hh
/// @brief Class definition for the universal hash algorithm for fixed vectors

// *************************************************************************

// Copyright© 2010 Texas A&M University, 
//                 College Station, Texas
//                 Contact: R Crosby <rwc@cs.tamu.edu>
//
// Copyright© 2003, 2004 by BiRC -- Bioinformatics Research Center
//                 University of Aarhus, Denmark
//                 Contact: Thomas Mailund <mailund@birc.dk>
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

// *************************************************************************

#ifndef UNIVHASHFIXEDVECTOR_HH
#define UNIVHASHFIXEDVECTOR_HH

#include <stdint.h>

#include "HashEncoder.hh"
#include "numbers.hh"

template < class keyT >
class UnivHashFixedVector
    : public HashEncoder< vector<keyT> >
{

    const unsigned        _vecSize;		  // Vector size

    unsigned              _nSlots;		  // Slots in hash table
    unsigned              _rawKeyLen;		  // Users key length in bytes
    unsigned              _keyLen;		  // Rounded up to long long size

    uint64_t              _mask;		  // Hash value mask
    unsigned              _shift;		  // Hash value shift count

    char *                _keyBuf;		  // Key is moved here...

    vector<uint64_t>      _ranVec;	          // Vector of random numbers

    static const unsigned _lls = sizeof(uint64_t); // Bytes in a 64 bit integer (duh)

public:

    virtual unsigned Encode ( const vector<keyT> & key );

    // Note the parameter to slots should be the bit width of the slot 
    // count value (e.g. 14 for 16284 slots).

    virtual void     Slots  ( const unsigned s )  
	{ _nSlots = s; 
	    _shift = 64 - _nSlots;
	    _mask = ( ( 1 << _nSlots ) - 1 ) << _shift; }

    UnivHashFixedVector     ( const unsigned vecSize );
    ~UnivHashFixedVector    () 
	{ delete[] _keyBuf; }

};

// *****************************************************************************
/// @brief Constructor for the encoder setting up the array of random numbers
///        used in the universal key algorithm
///
/// @param vecSize Size of the key vector

template < class keyT > 
UnivHashFixedVector < keyT > ::UnivHashFixedVector ( const unsigned vecSize )
    : _vecSize(vecSize)
{

    _rawKeyLen = _vecSize * sizeof(keyT);	  // Get key length in bytes

    // Round up to the nearest integral of the 64bit size
    // for the actual key buffer. This makes the key computation
    // algorithm easier
    _keyLen    = ( _rawKeyLen + _lls - 1 ) & (0 - _lls);
    
    _keyBuf    = new char[_keyLen];               // Allocate key buffer...
    memset(_keyBuf, 0, _keyLen);		  // And clear it

    // Get a vector of random numbers to use
    // The distribution of the random numbers isn't critical so 
    // just using the basic compiler function...
    for ( unsigned i = (_keyLen * 2)/ _lls;  i; i-- ) 
	_ranVec.push_back( (uint64_t)rand() | ( (uint64_t)rand() << 32 ) );

}

// *****************************************************************************
/// @brief Encode a hash key into an index
///
/// @param key Reference to the key
/// @return Index to use with the hash table

template < class keyT > 
unsigned
UnivHashFixedVector < keyT >::Encode (const vector<keyT> & key )
{

    // Copy input key to buffer...
    keyT * pos = (keyT*)_keyBuf;
    typename vector < keyT >::const_iterator i = key.begin();
    while ( i != key.end() ) *(pos++) = *(i++);

    // Process through the key accumulating the value code is based on 
    // Thorup, Mikkel (2009) "String hashing for linear probing" 
    uint64_t ha = 0;
    uint32_t* iVec = (uint32_t*)_keyBuf;
    for (unsigned i = 0; i < (_keyLen * 2) / _lls; i +=2 ) {
	uint64_t h = (iVec[i] + _ranVec[i]) * (iVec[i+1] + _ranVec[i+1]);
	ha = ha ^ h;
    }

    uint64_t hb = ( ha & _mask ) >> _shift;

    return hb;
}

#endif // UNIVHASHFIXEDVECTOR_HH
